// Package day_04_tree inorder_range
// @Title day_04_tree
// @Description  中序遍历
// @Author  == 琳琳也叫王木木 ==  2021/8/30 16:24
// @Create  2021/8/30 16:24
package day_04_tree

// InorderTraversal 使用递归  中序 遍历二叉树
func InorderTraversal(head *TreeNode) []int {
	var ans []int
	if head == nil {
		return ans
	}
	var recursion = func(root *TreeNode) {} // 定义一个函数类型
	recursion = func(root *TreeNode) {
		if root == nil {
			return
		}
		recursion(root.Left)
		ans = append(ans, root.Val)
		recursion(root.Right)
	}
	recursion(head)
	return ans
}

/**
使用栈实现中序遍历二叉树核心思想
1. 申请一个栈空间，先压根
2. 将所有左子树压栈，直到左子树为nil
3. 出栈一个元素，打印，压当前右子树
4. 重复直到栈为空
*/

// InorderTraversalStack 使用非递归 中序遍历二叉树
func InorderTraversalStack(head *TreeNode) []int {
	var ans []int
	if head == nil {
		return ans
	}
	var stack []*TreeNode
	cur := head
	for cur != nil || len(stack) > 0 {
		if cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		} else {
			cur = stack[len(stack)-1]    // 从栈中弹出一个元素
			stack = stack[:len(stack)-1] // 栈的长度减1
			ans = append(ans, cur.Val)
			cur = cur.Right
		}
	}
	return ans
}
